package com.peng.leetcode.heap;

import java.util.PriorityQueue;

/**
 * MaximumProduct
 * <p>
 * 628. 三个数的最大乘积
 *
 * @author: lupeng6
 * @create: 2021/1/20 14:21
 */
public class MaximumProduct {

    public static void main(String[] args) {
//        int[] arr = {1, 2, 3, 4};
//        int[] arr = {-100, -98, -1, 2, 3, 4};
        int[] arr = {3, 4, 0, 0, -1, -5};
        System.out.println(new MaximumProduct().maximumProduct(arr));
    }

    public int maximumProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        if (length == 3) {
            return nums[0] * nums[1] * nums[2];
        }
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(3, (a, b) -> b - a);
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(3);
        minHeap.offer(nums[0]);
        minHeap.offer(nums[1]);
        minHeap.offer(nums[2]);

        maxHeap.offer(nums[0]);
        maxHeap.offer(nums[1]);
        maxHeap.offer(nums[2]);


        for (int i = 3; i < length; i++) {
            int num = nums[i];
            if (minHeap.peek() < num) {
                minHeap.poll();
                minHeap.offer(num);
            }
            if (maxHeap.peek() > num) {
                maxHeap.poll();
                maxHeap.offer(num);
            }
        }
        Integer[] maxArr = minHeap.toArray(new Integer[0]);
        Integer[] minArr = maxHeap.toArray(new Integer[0]);
        int maxNum = maxArr[2];
        int num1 = maxArr[0] * maxArr[1] * maxArr[2];
        int num2 = maxNum * minArr[1] * minArr[2];
        return Math.max(num1, num2);
    }

}
